package aqs;

import java.util.*;

public class MaxQueue {
    private LinkedList<Integer> list = new LinkedList();
    private LinkedList<Integer> maxList = new LinkedList();

    public MaxQueue() {

    }

    public int max_value() {
        if (maxList.isEmpty()) {
            return -1;
        }
        return maxList.getLast();
    }

    public void push_back(int value) {
        if (maxList.isEmpty()) {
            maxList.addLast(value);
        } else {
            maxList.addLast(Math.max(maxList.getLast(), value));
        }
        list.addLast(value);
    }

    public int pop_front() {
        if (list.isEmpty()) {
            return -1;
        }
        maxList.pollFirst();
        return list.getFirst();
    }

}